package main.leetcode.primary.from001to100;

/**
 * 28.实现strStr()
 *
 * <p>实现 strStr() 函数。
 *
 * <p>给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 *
 * <p>示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
 *
 * <p>示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
 *
 * <p>说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 *
 * <p>对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex28 {
    public static void main(String[] args) {
        System.out.println(new ex28().strStr("hello", "ll"));
        //        System.out.println(new ex28().strStr("aaaaa", "bba"));
        //        System.out.println(new ex28().strStr("hellolll", "lll"));
        //        System.out.println(new ex28().strStr("mississippi", "issip"));
    }

    // 暴力法
    //    public int strStr(String haystack, String needle) {
    //        if ("".equals(needle)) {
    //            return 0;
    //        }
    //        char[] chars1 = haystack.toCharArray();
    //        char[] chars2 = needle.toCharArray();
    //        int m = chars1.length;
    //        int n = chars2.length;
    //        for (int i = 0; i <= m - n; ++i) {
    //            for (int j = 0; j < n; ++j) {
    //                if (chars2[j] != chars1[i + j]) {
    //                    break;
    //                }
    //                if (j == n - 1) {
    //                    return i;
    //                }
    //            }
    //        }
    //        return -1;
    //    }

    // kmp
    public int strStr(String haystack, String needle) {
        if ("".equals(needle)) {
            return 0;
        }
        if ("".equals(haystack)) {
            return -1;
        }
        int m = haystack.length();
        int n = needle.length();

        // 构造do[][]
        int[][] dp = new int[n][256];
        dp[0][needle.charAt(0)] = 1;
        for (int i = 1, X = 0; i < n; ++i) {
            for (int j = 0; j < 256; ++j) {
                // 复制匹配失败情况下的值
                // 在状态i下输入错误字符j时直接跳到重启状态X输入字符j的状态
                dp[i][j] = dp[X][j];
            }
            // 设置匹配成功情况下的值，即输入needle的第i个字符状态前推
            dp[i][needle.charAt(i)] = i + 1;
            // 更新重启状态，在原重启状态下输入needle的第i个字符后达到的状态
            X = dp[X][needle.charAt(i)];
        }
        // 开始匹配
        int s = 0;
        for (int i = 0; i < m; ++i) {
            s = dp[s][haystack.charAt(i)];
            // 到达终态
            if (s == n) {
                return i - n + 1;
            }
        }
        return -1;
    }
}
